"""
104. 二叉树的最大深度
简单
相关标签
premium lock icon
相关企业
给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。



示例 1：





输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：

输入：root = [1,null,2]
输出：2


提示：

树中节点的数量在 [0, 104] 区间内。
-100 <= Node.val <= 100
"""
from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:

    #自底向上
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root==None:
            return 0
        return max(self.maxDepth(root.left) , self.maxDepth(root.right)) + 1
    def maxDepth_2(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node: Optional[TreeNode],dept:int) -> int:
            if node is None:
                return dept
            nonlocal ans
            print("dept:",dept)
            lDept = dfs(node.left,dept+1)
            rDept = dfs(node.right,dept+1)
            ans = max(ans,max(lDept,rDept))
            return max(lDept,rDept)
        dfs(root,0)
        return ans

    # 自底向上
    def maxDepth_res1(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        l_depth = self.maxDepth(root.left)
        r_depth = self.maxDepth(root.right)
        return max(l_depth, r_depth) + 1

    #自上向底
    def maxDepth_res2(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if node is None:
                return
            depth += 1
            nonlocal ans
            ans = max(ans, depth)
            dfs(node.left, depth)
            dfs(node.right, depth)
        dfs(root, 0)
        return ans
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20)
    root.right.left = TreeNode(15)
    root.right.right = TreeNode(7)
    print(Solution().maxDepth_2(root))